Tiểu đoàn được thành lập ngày 1 tháng 5 năm 1948 tại vùng căn cứ Đồng Tháp Mười gồm lực lượng của Khu 8 và một bộ phận quan trọng của Trung đoàn 99 Bến Tre hợp thành, với tên "Tiểu đoàn liên quân lưu động". Tiểu đoàn làm lễ xuất quân ngày 5 tháng 7 tại căn cứ Giồng Luông, xã Đại Điền, huyện Thạnh Phú, tỉnh Bến Tre. Sau đó, vì thấy tên gọi "Tiểu đoàn Liên quân lưu động" dài, dễ lộ bí mật, trên cho đơn vị đổi tên thành Tiểu đoàn 307.

Trong năm đầu tiên, tiểu đoàn đã đánh thắng hai trận nổi tiếng ở Mộc Hóa và La Bang (Trà Vinh), mỗi trận tiêu diệt một tiểu đoàn địch.

Cuối năm 1949, Tư lệnh Khu 8 Trần Văn Trà phát động sáng tác ca khúc ca ngợi Tiểu đoàn 307 mới thành lập nhưng đã đánh thắng nhiều trận lớn. Nhà thơ Nguyễn Bính sáng tác bài thơ "Cửu Long Giang" đăng trên báo "Tổ quốc" - Khu 8, nhạc sĩ Nguyễn Hữu Trí phổ nhạc thành bài hát nổi tiếng "Tiểu đoàn ba lẻ bảy". Khi đó tiểu đoàn đang đóng trên bờ sông Nhị Mỹ, Cao Lãnh, Long Châu Sa. Bài hát có xuất xứ ở vùng Cao Lãnh, Ðồng Tháp sau phổ biến khắp Nam Bộ, lan rất nhanh trong bộ đội và cả trong nhân dân. Tối 1 tháng 10 năm 1950, lần đầu tiên bài hát được phát sóng trên Đài Tiếng nói Nam Bộ kháng chiến do Tổ quân nhạc Khu 8 trực tiếp biểu diễn.[1] Với ca từ chắc nhịp, dễ nhớ "Ai đã từng đi qua sông Cửu Long Giang, Cửu Long giang sóng trào nước xoáy. Ai đã từng nghe tiếng Tiểu đoàn, tiếng Tiểu đoàn 307! Buổi xuất quân Tiểu đoàn năm ấy, cả Tiểu đoàn thề dưới sao vàng, người chiến sĩ tiếc gì máu rơi, buổi xuất quân Tiểu đoàn năm ấy nguyện một lòng gìn giữ non sông…", bài hát đã đi vào lòng nhiều thế hệ người Việt Nam.

Tính đến năm 1954, Tiểu đoàn 307 đã hơn đánh 110 trận lớn nhỏ. Sau Hiệp định Genève, 1954, Tiểu đoàn 307 hành quân về tiếp quản thị xã Cà Mau và thị trấn Tắc Vân, sau đó xuống tàu tập kết ra Bắc, được tái tổ chức lại thành Tiểu đoàn 7, thuộc Trung đoàn 3, Sư đoàn 330[2] đóng quân tại Thanh Hóa dưới quyền chỉ huy của Sư đoàn trưởng Đồng Văn Cống.

Lịch sử của Tiểu đoàn 307 thời Chiến tranh Đông Dương có ba người tiểu đoàn trưởng. Tiểu đoàn trưởng đầu tiên của Tiểu đoàn 307 là ông Ðỗ Huy Rừa quê ở làng La Ngạn, xã Yên Đồng, huyện Ý Yên, tỉnh Nam Định. Ông đã chỉ huy Tiểu đoàn tại các trận Mộc Hóa, La Bang, ông hy sinh năm 1949. Kế nhiệm ông là Nguyễn Văn Tiên, người về sau trở thành một trong những chỉ huy không quân nổi tiếng, được thăng đến hàm Trung tướng. Tiểu đoàn trưởng cuối cùng trước lúc Tiểu đoàn 307 lên đường tập kết ra Bắc là ông Phạm Hồng Sơn, quê ở Hà Tây.[3]

• Đỗ Huy Rừa, Tiểu đoàn trưởng 1948-1949
• Nguyễn Văn Sỹ, Tiểu đoàn phó 1948-?
• Hồng Long hay Nguyễn Sĩ Thao, Chính trị viên từ 1943,
• Nguyễn Văn Tiên, Tiểu đoàn trưởng (1949-1952). Chính trị viên kiêm Bí thư Đảng ủy (1952-1954).
• Đào Ngọc Sới, Tiểu đoàn phó (1921-1990) - 1944-1954
• Phạm Hồng Sơn, Tiểu đoàn trưởng 1952-1954
• Vũ Đình Thông, Tiểu đoàn phó ?-?